#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> st;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (st.empty() || height[st.top()] >= height[i])
            {
                st.push(i);
                continue;
            }

            while (!st.empty() && height[st.top()] < height[i])
            {
                int t1 = st.top();
                st.pop();
                if (st.empty())break;
                int t2 = st.top();
                int w = i - t2 - 1;
                // cout<<height[t1]<<" "<<height[t2]<<"---";
                int h = min(height[i], height[t2]) - height[t1];
                // cout<<h*w<<" "<<h<<" "<<w<<" "<<i<<endl;
                ans += h * w;

            }
            st.push(i);
        }
        return ans;
    }
};